'''
https://leetcode.cn/problems/scramble-string/
scramble: 攀爬，爬行
在这里的意思是扰乱
'''
from functools import cache


class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        @cache
        def f(i, j, size):
            if size == 1:
                return s1[i] == s2[j]
            # print(f'{i, i+size-1}, {j, j+size-1}')
            # 正向匹配
            for s in range(1, size):
                if f(i, j, s) and f(i + s, j + s, size - s):
                    return True
            # 错位匹配
            for s in range(1, size):
                # ...111 11111...
                # ...22222 222...
                if f(i, j + size - s, s) and f(i + s, j, size - s):
                    return True
            return False

        return f(0, 0, len(s1))

    # dp打表
    def isScramble2(self, s1: str, s2: str) -> bool:
        n = len(s1)
        dp = [[[False] * (n+1) for _ in range(n)] for _ in range(n)]
        # if size == 1: then dp[i][j][1] = s1[i] == s2[j]
        for i in range(n):
            for j in range(n):
                dp[i][j][1] = s1[i] == s2[j]
        # 第一维度第二维度依赖后边的， 第三维度依赖后边的和前边的
        for size in range(2, n + 1):
            for i in range(n - size + 1):
                for j in range(n - size + 1):
                    res = False
                    for s in range(1, size):
                        if dp[i][j][s] and dp[i + s][j + s][size - s]:
                            res = True
                            break
                    if not res:
                        for s in range(1, size):
                            if dp[i][j + size - s][s] and dp[i + s][j][size - s]:
                                res = True
                                break
                    dp[i][j][size] = res
        return dp[0][0][len(s1)]


s1 = 'abca'
s2 = 'caba'
print(Solution().isScramble(s1, s2))
